package com.scott.BinarySearchTree;

/**
 * 二叉搜索树
 */
public class BinarySearchTree<T extends Comparable<T>> {


    public BinarySearchTree() {
        root = null;
    }

    /**
     * 根节点
     */
    private BSTNode<T> root;

    /**
     * 新增节点
     *
     * @param key 新节点
     */
    public synchronized void insert(T key) {
        //构造二叉树节点，新的二叉树节点都没有左节点和右节点,而父节点未知
        BSTNode<T> newNode = new BSTNode<T>(key, null, null, null);

        insert(this, newNode);
    }

    private void insert(BinarySearchTree<T> tree, BSTNode<T> newNode) {
        int cmp; //比较数
        BSTNode<T> parent = null; //新节点的父节点
        BSTNode<T> x = tree.root; //循环遍历值

        //查找newNode应该往哪个节点下添加，也就是定位他的parent
        while (x != null) {
            parent = x;
            cmp = newNode.key.compareTo(x.key);
            //如果新值较小，则继续往左边下面找，反之在右边找
            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                return;//如果相等，则说明已经有此元素，不在添加
            }
        }

        //将查找的parent赋值给新的节点
        newNode.parent = parent;
        //如果找到的父节点为空，则说明是第一个节点，直接将新值复制给root
        if (parent == null) {
            tree.root = newNode;
        } else {
            //更新父节点的左右节点信息 如果父节点的值比新值大，则更新父节点的左子节点为新值，反之更新为右子节点
            if (parent.key.compareTo(newNode.key) > 0) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
        }

    }

    /*
     * 删除结点(z)，并返回被删除的结点
     *
     * 参数说明：
     *     bst 二叉树
     *     z 删除的结点
     */
    private BSTNode<T> remove(BinarySearchTree<T> bst, BSTNode<T> z) {
        BSTNode<T> x = null;
        BSTNode<T> y = null;

        if ((z.left == null) || (z.right == null))
            y = z;
        else
            y = successor(z);

        if (y.left != null)
            x = y.left;
        else
            x = y.right;

        if (x != null)
            x.parent = y.parent;

        if (y.parent == null)
            bst.root = x;
        else if (y == y.parent.left)
            y.parent.left = x;
        else
            y.parent.right = x;

        if (y != z)
            z.key = y.key;

        return y;
    }

    /**
     * 删除结点(z)，并返回被删除的结点
     * <p>
     * 参数说明：
     * tree 二叉树的根结点
     * z 删除的结点
     */
    public synchronized void remove(T key) {
        BSTNode<T> z, node;

        if ((z = search(root, key)) != null)
            if ((node = remove(this, z)) != null)
                node = null;
    }


    private BSTNode<T> search(BSTNode<T> x, T key) {
        if (x == null)
            return x;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }

    /**
     * (递归实现)查找"二叉树x"中键值为key的节点
     */
    public BSTNode<T> search(T key) {
        return search(root, key);
    }


    private void destroy(BSTNode<T> tree) {
        if (tree == null)
            return;

        if (tree.left != null)
            destroy(tree.left);
        if (tree.right != null)
            destroy(tree.right);

        tree = null;
    }

    /**
     * 销毁二叉树
     */
    public void clear() {
        destroy(root);
        root = null;
    }

    private BSTNode<T> maximum(BSTNode<T> tree) {
        if (tree == null)
            return null;

        while (tree.right != null)
            tree = tree.right;
        return tree;
    }

    /**
     * 查找最大结点：返回tree为根结点的二叉树的最大结点。
     */
    public T maximum() {
        BSTNode<T> p = maximum(root);
        if (p != null)
            return p.key;

        return null;
    }


    private BSTNode<T> minimum(BSTNode<T> tree) {
        if (tree == null)
            return null;

        while (tree.left != null)
            tree = tree.left;
        return tree;
    }

    /**
     * 查找最小结点：返回tree为根结点的二叉树的最小结点。
     */
    public T minimum() {
        BSTNode<T> p = minimum(root);
        if (p != null)
            return p.key;

        return null;
    }

    /**
     * 前序遍历
     */
    public void preTraverse() {
        preTraverse(root);
    }

    /**
     * 中序遍历
     */
    public void inTraverse() {
        inTraverse(root);
    }

    /**
     * 后序遍历
     */
    public void postTraverse() {
        postTraverse(root);
    }

    private void preTraverse(BSTNode<T> tree) {
        if (tree != null) {
            System.out.print(tree.key + " ");
            preTraverse(tree.left);
            preTraverse(tree.right);
        }
    }

    private void inTraverse(BSTNode<T> tree) {
        if (tree != null) {
            inTraverse(tree.left);
            System.out.print(tree.key + " ");
            inTraverse(tree.right);
        }
    }

    private void postTraverse(BSTNode<T> tree) {
        if (tree != null) {
            postTraverse(tree.left);
            postTraverse(tree.right);
            System.out.print(tree.key + " ");
        }
    }

    /**
     * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
     */
    public BSTNode<T> preDecessor(BSTNode<T> x) {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (x.left != null)
            return maximum(x.left);

        // 如果x没有左孩子。则x有以下两种可能：
        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.left)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    /**
     * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
     */
    public BSTNode<T> successor(BSTNode<T> x) {
        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (x.right != null)
            return minimum(x.right);

        // 如果x没有右孩子。则x有以下两种可能：
        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.right)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    /**
     * 二叉树节点
     *
     * @param <T>
     */
    private class BSTNode<T extends Comparable<T>> {
        /**
         * 键
         */
        T key;

        /**
         * 左节点
         */
        BSTNode<T> left;

        /**
         * 右节点
         */
        BSTNode<T> right;

        /**
         * 父节点
         */
        BSTNode<T> parent;

        public BSTNode(T key, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }
}
